import org.w3c.dom.Node;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-13
 * Time: 20:24
 */
//单链表实现栈或队列
public class LinkedListToStackAndQueue {
    //泛型节点类，适用于所有类型
    public static class Node<V>{
        public  V val;
        public Node<V> next;
        public Node(V val){
            this.val = val;
            next = null;
        }
    }
    
    //实现队列，队列就是先进先出，先遍历到的节点先加队列，先遍历到的也是先弹出队列
    public static class MyQueue<V>{
        //队列头结点和尾结点，大小
        private Node<V> head;
        private Node<V> tail;
        private int size;
        //构造方法
        public MyQueue(){
            head=null;
            tail = null;
            size=0;
        }
        //判空
        public boolean isEmpty(){
            return size==0;
        }
        //计算大小
        public int size(){
            return size;
        }
        
        //入队
        public void offer(V val) {
            Node<V> cur=new Node<>( val );
            if(head == null){
                head = cur;
                tail = cur;
            }else {
                tail.next=cur;
                tail=cur;
            }
            size++;
        }
        //出队
        public V poll() {
            V ret=null;
            if(head!=null){
                ret= head.val;
                head = head.next;
                size--;
            }
            if (head == null) {
                tail=null;
            }
            return ret;
        }
        //获取队首
        public V peek(){
            V ret = null;
            if(head != null){
                ret = head.val;
            }
            return ret;
        }
    }
    
    //单链表实现栈
    public static class MyStack<V>{
        //只需要一个节点
        private Node<V> head;
        private int size;
        public MyStack(){
            head=null;
            size=0;
        }
        
        //判空
        public boolean isEmpty(){
            return size==0;
        }
        //大小
        public int size(){
            return size;
        }
        
        //入栈
        public void push(V val){
            Node<V> cur=new Node<V>( val );
            if (head == null) {
                head=cur;
            }else{
                cur.next=head;
                head=cur;
            }
            size++;
        }
        
        //出栈
        public V pop(){
            V ret=null;
            if(head!=null){
                ret= head.val;
                head=head.next;
                size--;
            }
            return ret;
        }
        //获取栈顶元素
        public V peek(){
            V ret=null;
            if(head!=null){
                ret=head.val;
                return ret;
            }
            return null;
        }
    }
    public static void testQueue() {
        MyQueue<Integer> myQueue = new MyQueue<>();
        Queue<Integer> test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myQueue.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myQueue.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myQueue.offer(num);
                test.offer(num);
            } else if (decide < 0.66) {
                if (!myQueue.isEmpty()) {
                    int num1 = myQueue.poll();
                    int num2 = test.poll();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myQueue.isEmpty()) {
                    int num1 = myQueue.peek();
                    int num2 = test.peek();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myQueue.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myQueue.isEmpty()) {
            int num1 = myQueue.poll();
            int num2 = test.poll();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }
    
    public static void testStack() {
        MyStack<Integer> myStack = new MyStack<>();
        Stack<Integer> test = new Stack<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myStack.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myStack.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myStack.push(num);
                test.push(num);
            } else if (decide < 0.66) {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.pop();
                    int num2 = test.pop();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.peek();
                    int num2 = test.peek();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myStack.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myStack.isEmpty()) {
            int num1 = myStack.pop();
            int num2 = test.pop();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }
    
    public static void main(String[] args) {
        testQueue();
        testStack();
    }
}
